package org.liaohailong.helloworld.example;

/**
 * Author: liaohailong
 * Time: 2021/8/12 14:52
 * Describe:
 */
public class FT {


    // LC 最低加油次数
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int N = stations.length;

        // dp[i] 表示加了第i次油之后，走的最远的距离
        long[] dp = new long[N + 1];
        dp[0] = startFuel;
        for (int i = 0; i < N; i++) {
            for (int j = i; j >= 0; j--) {
                // 如果加j次油之后，能够到达这个加油站，就可以计算出j+1次的距离
                if (dp[j] >= stations[i][0]) {
                    // max比较判断，可能出现中间跨加油站加油，并能开的更远的情况
                    dp[j + 1] = Math.max(dp[j + 1], dp[j] + (long) stations[i][1]);
                }
            }
        }

        for (int i = 0; i < dp.length; i++) {
            if (dp[i] >= target) return i;
        }

        return -1;
    }

}
